翻訳と辞書
Words near each other
・ NKリサイクル
・ NKリンパ球
・ NKルダル・ヴェレニエ
・ NKロコモティヴァ
・ NKロコモティヴァ・ザグレブ
・ NKヴァラジュディン
・ NKヴァルテクス
・ NKヴァルテクス・ヴァラジュディン
・ NKヴァルテクス・ヴァラジン
・ NK細胞
NL (計算複雑性理論)
・ NLA麻酔法、神経遮断鎮痛療法
・ NLTテクノロジー
・ NMB48 げいにん!
・ NMB48 げいにん!!!3
・ NMB48 げいにん!!2
・ NMB48 げいにん!THE MOVIE
・ NMB48 げいにん!THE MOVIE お笑い青春ガールズ!
・ NMB48 げいにん!THE MOVIE リターンズ 卒業!お笑い青春ガールズ!!新たなる旅立ち
・ NMB48 りぃちゃんのがんばり〜な!


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

NL (計算複雑性理論) : ミニ英和和英辞書
NL (計算複雑性理論)[えぬえる]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [けい]
  1. (n,n-suf) plan 
計算 : [けいさん]
  1. (n,vs) (1) calculation 2. reckoning 3. count 4. (2) forecast 
: [ふく]
  1. (n,pref) double 2. compound 
複雑 : [ふくざつ]
  1. (adj-na,n) complexity 2. complication 
: [ざつ]
  1. (adj-na,n) rough 2. crude 
: [り]
 【名詞】 1. reason 
理論 : [りろん]
 【名詞】 1. theory 
: [ろん]
 【名詞】 1. (1) argument 2. discussion 3. dispute 4. controversy 5. discourse 6. debate 7. (2) theory 8. doctrine 9. (3) essay 10. treatise 1 1. comment

NL (計算複雑性理論) : ウィキペディア日本語版
NL (計算複雑性理論)[えぬえる]
NL(えぬえる、)は、計算複雑性理論における決定問題複雑性クラスの一つである。非決定性チューリングマシン対数規模の記憶領域を使って解ける問題がこのクラスに属する。
NLLを一般化したものである。L決定性チューリングマシンでの対数領域問題のクラスである。決定性チューリングマシンは非決定性チューリングマシンに含まれるため、LNL に含まれる。
NL非決定性領域(NSPACE)の計算資源記法で形式的に定義でき、NL = NSPACE(log ''n'') となる。
計算複雑性理論の研究により、このクラスと他の複雑性クラスの関係が明らかとなり、必要な計算資源も明らかとなってきた。一方、アルゴリズムの研究によって、対数領域で解ける問題も明らかとなってきつつある。しかし、計算複雑性理論の他の分野と同様、NLについての重要な部分は未解決である。
NL確率的定義(後述)を指して RL と呼ぶこともある。しかし、RLという名称はRLPという複雑性クラスの別名として使われることが多い(RLPとは、確率的チューリングマシンで対数領域と多項式時間で解ける問題のクラス)。
== NL完全問題 ==
ある複雑性クラスに属する最も難しい問題を指して完全問題という。直観的には、完全問題を効率的に解く方法が判っていれば、それを使ってそのクラスのあらゆる問題を解くことが出来る。すなわち、完全問題はその複雑性クラスの能力の程度を示すものである。
NL完全であることが判っている問題はいくつかある。STCON問題(有向グラフの2点間の経路の有無を問う問題)と2元充足可能性問題NL完全である。2元充足可能性問題とは、連言標準形論理式の各節(論理和で表される部分)が2つの変数で構成されているとき、その論理式を真とする変数値の組み合わせが存在するかどうかを問う問題である。以下にそのような論理式の例を示す。なお、~(チルダ)は「否定」を意味する。
:(''x''1 or ~''x''3) and (~''x''2 or ''x''3) and (~''x''1 or ~''x''2)

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「NL (計算複雑性理論)」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.